Quadtree data structures are useful for storing data. One such data structure is a geo-spatial quadtree that stores two dimensional information related to the Earth or other geographical data. Each node of the geo-spatial quadtree includes four children, where each child covers a fourth of the area of the parent.
When storing three dimensional information however, a geo-spatial quadtree will not suffice. In this case, an octree data structure may be useful. An octree is a three dimensional representation of a quadtree, where each node has eight children instead of four. Imagining a parent node of the octree as covering a cubic volume, each child node covers an eighth of the cubic volume. When three dimensional information about a space is stored, such as in a representation of the Earth, no three dimensional information may be present for several quadtree or octree levels. Because of this, the upper levels of the octree may contain empty nodes, increasing the indexing and/or parsing overheads without providing helpful data.